package com.yww.leetcode.heap;

import com.yww.datastructure.heap.Heap;

/**
 * @author yww
 * @description 703. 数据流中的第 K 大元素
 * @since 2024/2/7 21:48
 */
public class KthLargest703 {
    //KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。k:第k大的元素
    //int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
    Heap minHeap;

    /**
     * 解题思路
     * <p>
     * 1. 向小顶堆放入前k个元素
     * 2. 剩余元素
     * 1. 若 <= 堆顶元素，则略过
     * 2. 若 > 堆顶元素，则替换堆顶元素
     * 3. 这样小顶堆始终保留的是目前为止，前 k 大 的元素
     * 4. 循环结束，堆顶元素即为 第 K 大 元素
     */
    public KthLargest703(int k, int[] nums) {
        minHeap = new Heap(false, k);
        for (int num : nums) {
            add(num);
        }
    }

    /**
     * 解题思路
     * 1. 如果堆未满，加入堆
     * 2. 如果堆满，如果val > 堆顶 替换堆顶，返回堆顶即可
     */
    public int add(int val) {
        if (!minHeap.isFull()) {
            minHeap.offer(val);
        } else if (val > minHeap.peek()) {
            minHeap.replace(val);
        }
        return minHeap.peek();
    }
}
